package class02;

/**
 * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这一种数
 * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
 *
 * <a href="https://leetcode.cn/problems/single-number/">136. 只出现一次的数字</a>
 * <a href="https://leetcode.cn/problems/single-number-iii/">260. 只出现一次的数字 III</a>
 */
public class Code01_EvenTimesOddTimes {
    // 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这一种数
    public static int printOddTimesNum1(int[] arr) {
        int eor = 0;
        // 利用异或运算的结合律可以得出
        for (int num : arr) {
            eor ^= num;
        }
        return eor;
    }

    // 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        // 首先利用异或运算的结合律找出奇数次的数
        // 那么得出来的eor就是两个奇数异或的结果，例如 eor = a ^ b
        for (int num : arr) {
            eor ^= num;
        }
        // 如何分开这两个数，要知道偶数次的数终将会被异或为0
        // 那么如果eor不为0，在eor上的某一位一定会有一位为1
        // 我们找到eor上某位为1的那个数，假设eor上，第3位为1，那么根据第3位为1的数
        // arr数组上可以分为两类，第一种是第3位为1的数为一类，第二种是第3为为0的数为一类
        // 分为两类后，该问题就变成了，如何在一个数组中找到出现一种奇数次的数了
        // 为什么？因为其他数终究会被异或为0，两个不同的数异或一定会有某一位不相同一个为0一个为1，才会被异或
        // 所以利用异或原理，可以将一个数组中所有某一位为1的数分一类，所有某一位为0的数分一类
        // 将这两类数组，做数组中找到出现一种奇数次的数，那么两类数组都做异或运算，最终会各自得出出现奇数次的那个数了
        int rightOne = eor & (~eor + 1);  // 取出最右边第一个为1的数，右边等式也可以写成 eor & (-eor)
        int onlyOne = 0;  // 用来保留某一类出现的奇数次的结果
        for (int num : arr) {
            // 这里保留的是某一位为0的那一类
            if ((num & rightOne) == 0) {
                onlyOne ^= num;
            }
        }
        // 在最后得出了某一位为0的那一类出现奇数次的结果
        // 想要得出另一类中奇数次的结果，只需要用eor异或出来即可
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8};
        printOddTimesNum2(arr);
    }
}
